// https://www.lintcode.com/problem/first-position-of-target/my-submissions

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        while (start + 1 < end)
        {
            int mid = (end - start) / 2 + start;            
            if (nums[mid] < target) //注意要小于
            {
                start = mid;
            }
            else
            {
                end = mid;
            }
        }
        if (nums[start] == target)
        {
            return start;
        }
        else if (nums[end] == target)
        {
            return end;
        }
        return -1;
    }
};